#include<iostream>
using namespace std;
#include<vector>
#include<string>
class Solution {
public:
    int l, r;
    string path;
    vector<string> ans;
    void dfs() {
        if (l == 0 && r == 0) {
            ans.push_back(path);
            return;
        }
        if (l > 0) {
            --l;
            path += '(';
            dfs();
            path.pop_back();
            ++l;
        }
        if (l < r) {
            --r;
            path += ')';
            dfs();
            path.pop_back();
            ++r;
        }
        return;
    }
    vector<string> generateParenthesis(int n) {
        l = r = n;
        dfs();
        return ans;
    }
};